import java.util.*;

public class Test {

    public static List<String> topKFrequent(String[] words, int k) {
        // 1.统计每个单词出现的次数
        Map<String,Integer> map=new HashMap<>();
        for(String word:words) {
            if(map.get(word)==null) {
                //第一次出现
                map.put(word,1);
            }else {
                int val=map.get(word);
                map.put(word,val+1);
            }
        }
        // 2.通过上述代码，已将出现次数存储在map中。接下来遍历map，建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //当出现次数相同时，按大根堆排列，方便后面进行逆置
                if(o1.getValue().compareTo(o2.getValue())==0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for(Map.Entry<String,Integer> entry:map.entrySet()) {
            if(minHeap.size()<k) {
                minHeap.offer(entry);
            } else {
                //此时，堆已经构建完成，再往里放元素时，需要与堆顶元素进行比较
                Map.Entry<String,Integer> top=minHeap.peek();
                if(top.getValue().compareTo(entry.getValue())==0) {
                    //val相同时，比较字典序
                    if(top.getKey().compareTo(entry.getKey())>0) {
                        //将堆顶元素出出去
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    if (top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

        List<String> ret=new ArrayList<>();
        for(int i=0;i<k;i++) {
            Map.Entry<String,Integer> tmp=minHeap.poll();
            ret.add(tmp.getKey());//将符合要求的字符串存进链表中
        }
        //对链表进行逆置，使得按照从大到小排列
        Collections.reverse(ret);
        return ret;
    }

    public static void main(String[] args) {
        String[] words= {"i","love","leetcode","i","love","coding"};
        List<String> ret=topKFrequent(words,1);
        System.out.println(ret);
    }



    //统计10个数据中，数据出现的次数
    public static void main3(String[] args) {
        //此题要用map
        int[] array={1,2,4,1,6,2,8,7,6,10};

        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<array.length;i++){
            if(map.get(array[i])==null) {   //第一次出现
                map.put(array[i],1);
            }else { //重复数据
                int val=map.get(array[i]);//先获取一下原来的出现次数
                map.put(array[i],val+1);
            }
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()) {
            System.out.println("数字："+entry.getKey()+",次数："+entry.getValue());
        }
    }

    // 给你10个数据，对其进行去重
    public static void main2(String[] args) {
        int[] array={1,2,4,1,6,2,8,7,6,10};
        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i<array.length;i++){
            set.add(array[i]);
        }
        System.out.println(set);//set天然去重
    }

    // 找出10个数据中第一个重复数据
    public static void main1(String[] args) {
        int[] array={1,2,4,1,6,2,8,7,6,10};
        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i<array.length;i++){
            if(set.contains(array[i])){
                System.out.println(array[i]);
                return;
            }else {
                set.add(array[i]);
            }
        }
    }

    //旧键盘打字
    public static void Main(String[] args) {
        Scanner in=new Scanner(System.in);
        while(in.hasNextLine()) {
            String str1=in.nextLine();
            String str2=in.nextLine();
            func(str1,str2);//str1和str2分别为输入的和输出的
        }
    }

    public static void func(String str1,String str2) {
        HashSet<Character> set1=new HashSet<>();
        HashSet<Character> setBroken=new HashSet<>();
        //遍历s
        for(char ch:str2.toUpperCase().toCharArray()) {
            set1.add(ch);
        }
        //遍历str1,与集合中的字符进行比较,看集合中是否存在
        for(char ch:str1.toUpperCase().toCharArray()) {
            //只有当set1中没有，且没有被打印过的字符才会被打印
            if(!set1.contains(ch) && !setBroken.contains(ch)) {
                System.out.print(ch);
                setBroken.add(ch);//将打印过的字符再放入setBroken
            }
        }
    }

    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set=new HashSet<>();
        int count=0;//代表石头中宝石的数量
        //遍历宝石字符串，将代表宝石的字符存进去
        for(int i=0;i<jewels.length();i++) {
            char ch=jewels.charAt(i);
            set.add(ch);
        }
        for(int i=0;i<stones.length();i++) {
            char ch=stones.charAt(i);
            if(set.contains(ch)) {
                count++;
            }
        }
        return count;
    }

    /*


    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map=new HashMap<>();
        //第一次遍历原链表
        Node cur=head;
        while(cur!=null) {
            //创建新节点
            Node node=new Node(cur.val);
            map.put(cur,node);//存储映射关系
            cur=cur.next;
        }
        //循环结束，在map中就已经存储了老节点和新节点的映射关系
        //再次遍历链表
        cur=head;
        while(cur!=null) {
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }*/

    /**
     * 没有异或快
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i<nums.length;i++) {
            if(!set.contains(nums[i])) {
                set.add(nums[i]);
            }else {
                set.remove(nums[i]);
            }
        }
        //需要再遍历一遍数组来找到数组中还剩下的那个元素
        for(int i=0;i<nums.length;i++) {
            if(set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }

}
